import { testSort, measureSort } from "./utils";

function insertSort(arr: number[]): number[] {
  let n = arr.length;
  for (let i = 1; i < n; i++) {
    // i节点值，拿出来
    const newNum = arr[i];
    // i前标，拿出来
    let j = i - 1;
    while (arr[j] > newNum && j >= 0) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j+1] = newNum;
  }

  return arr;
}

// 测试
testSort(insertSort);
// 测试时间
measureSort(insertSort, 100000);


